package com.base.graph;

import java.util.Arrays;

/**
 * @ClassName: Dijkstra
 * @Description: 狄杰斯特拉算法，求最短路径问题
 * @author: li
 * @Date: 2021/8/23 5:00 下午
 */
public class Dijkstra {
    //代表距离为无穷，即两点之间无联通
    public static final int M = 1000;

    public static void main(String[] args) {
        // 二维数组每一行分别是 A、B、C、D、E 各点到其余点的距离,
        // A -> A 距离为0, 常量M 为正无穷
        int[][] weight1 = {
                {0, 4, M, 2, M},
                {4, 0, 4, 1, M},
                {M, 4, 0, 1, 3},
                {2, 1, 1, 0, 7},
                {M, M, 3, 7, 0}
        };

        int[] save = dijkstra(weight1, 0);
        System.out.println(Arrays.toString(save));
    }

    public static int[] dijkstra(int[][] graph, int start) {
        // 顶点个数
        int n = graph.length;
        //保存start 到所有结点的最短路径
        int[] savePath = new int[n];
        // 对于无向图需要保存是否访问这一状态
        // 保存结点的访问状态,true表示已经求出start当i结点的最短路径
        boolean[] visited = new boolean[n];

        //用于展示路径
        String[] path = new String[n];
        for (int i = 0; i < n; i++) {
            path[i] = start + "-->" + i;
        }

        //当前start到start结点的距离为0，并且已经访问。
        savePath[start] = 0;
        visited[start] = true;

        for (int count = 1; count < n; count++) {
            //选出距离start最近的点 k
            int k = -1;
            // 点k到start的距离
            int dmin = Integer.MAX_VALUE;

            for (int i = 0; i < n; i++) {
                if (!visited[i] && graph[start][i] < dmin) {
                    k = i;
                    dmin = graph[start][i];
                }
            }

            //将新选出来的点标记为访问，并将其路径加入到savePath

            savePath[k] = dmin;
            visited[k] = true;

            //  以k为中间点，修正各点到start的距离
            for (int i = 0; i < n; i++) {
                if (!visited[i] && graph[start][k] + graph[k][i] < graph[start][i]) {
                    graph[start][i] = graph[start][k] + graph[k][i];
                    path[i] = path[k] + "-->" + i;
                }

            }


        }

        for (int i = 0; i < n; i++) {
            System.out.println("从" + start + "到" + i + "最短路径是:" + path[i]);
        }
        return savePath;

    }
}
